package com.samxcode.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the
 * input string is valid.
 * 
 * The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]"
 * are not.
 * 
 * @author Sam
 *
 */
public class ValidParentheses {

    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        //add an unrelated element to avoid to check whether the stack is empty
        stack.add('0');
        for (Character ch : s.toCharArray()) {
            switch (ch) {
            case ')':
                if (stack.removeLast() != '(') {
                    return false;
                }
                break;
            case ']':
                if (stack.removeLast() != '[') {
                    return false;
                }
                break;
            case '}':
                if (stack.removeLast() != '{') {
                    return false;
                }
                break;
            default:
                stack.addLast(ch);
                break;
            }
        }
        if (stack.getLast() == '0') {
            return true;
        }
        return false;
    }
}
